FIG. 1 is a block diagram of a basic Motion Picture Experts Group (MPEG) encoding scheme. The video portion of MPEG-1 encoding is described in detail in International Standards Organization (ISO) document IS 11172, Part 2, “Video” Published Jan. 8, 1990. Subsequent versions of the MPEG video encoding standards (e.g., MPEG-2, MPEG-4) also exist.
If necessary, analog source data is converted by analog-to-digital converter 100 to digital data. The digital data is processed using discrete cosine transform 110. In general, a discrete cosine transform (DCT) is a technique for decomposing a block of data into a weighted sum of spatial frequencies. Each spatial frequency pattern has a corresponding coefficient, which is the amplitude used to represent the contribution of the spatial frequency pattern in the block of data being analyzed. DCT operations and the various implementations are known in the art. See, for example, William B. Pennebaker and Joan L. Mitchell, “JPEG: Still Image Data Compression Standard,” Van Nostrand Reinhold, 1993 or K. R. Rao and P. Yip, “Discrete Cosine Transform,” Academic Press, 1990.
In a typical MPEG encoding scheme, a frame of an image is divided into macroblocks. Each 16 pixel by 16 pixel macroblock (which is further divided into four 8 by 8 blocks) has 256 bytes of luminance (Y) data for the 256 pixels of the macroblock. The blue chrominance (U) and red chrominance (V) data for the pixels of the macroblock are communicated at ¼ resolution, or 64 bytes of U data and 64 byes of V data for the macroblock and filtering is used to blend pixel colors.
The macroblock data output by DCT 110 is further processed by quantization 120. A DCT coefficient is quantized by dividing the DCT coefficient by a nonzero positive integer called a quantization value and rounding the quotient to the nearest integer. See, for example, Joan L. Mitchell, et al., “MPEG Video Compression Standard,” Kluwer Academic Publishers, 1996, pages 46–49. The quantized macroblock coefficients are converted from a two-dimensional format (e.g., 16×16 block) to a one-dimensional sequence using a zig-zag scanning order. The sequence resulting from zig-zag transform 130 is a compressible bitstream.
The bitstream output by zig-zag transform 140 is run/level encoded by run/level encoder 140, which converts strings of zeros and non-zero coefficients output from zig-zag transform 130 into number pairs. In typical implementations, run/level code table 150 provides run/level codes for common strings of zeros and associated non-zero coefficients. For combinations not in run/level code table 150, run/level encoder 140 determines the proper run/level code. A runaevel code table that can be used is described in Mitchel, Joan L., et al., “MPEG Video Compression Standard,” pages 228–230, published by Kluwer Academic Publishers, 1996. Strings of number pairs are the MPEG-encoded bitstream that carries sufficient information to reconstruct a motion video.
Because of the many steps and the complexity of MPEG encoding as described with respect to FIG. 1, MPEG encoding typically cannot be performed in real time while providing significant levels of compression. Therefore, it is desirable to provide a more efficient MPEG encoding scheme.